//给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。 
//
// 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。 
//
// 你可以返回任何满足上述条件的数组作为答案。 
//
// 
//
// 示例： 
//
// 输入：[4,2,5,7]
//输出：[4,5,2,7]
//解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= A.length <= 20000 
// A.length % 2 == 0 
// 0 <= A[i] <= 1000 
// 
//
// 
// Related Topics 排序 数组

package leetcode.editor.cn;
public class SortArrayByParityIi {
    public static void main(String[] args) {
        Solution solution = new SortArrayByParityIi().new Solution();
        printArray(solution.sortArrayByParityII(new int[]{4,2,5,7}));

    }

    public static void printArray(int array[]) {
        if (array != null) {
            for (int i : array) {
                System.out.println(i);
            }
            System.out.println("---------------------- end");
        }
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] sortArrayByParityII(int[] A) {
        if (null == A) {
            return null;
        }
        if (A.length == 0 || A.length == 1) {
            return A;
        }

        int odd[] = new int[A.length];
        int oddLength = 0;
        int oddIndex = 0;
        int single[] = new int[A.length];
        int singleLength = 0;
        int singleIndex = 0;

        for (int i = 0; i < A.length; i++) {
            int current = A[i];
            if (current % 2 == 0) {
                odd[oddIndex++] = current;
                oddLength++;
            } else {
                single[singleIndex++] = current;
                singleLength++;
            }
        }

        singleIndex = 0;
        oddIndex = 0;
        for (int i = 0; i < A.length; i++) {
            if (i % 2 == 0) {
                A[i] = odd[oddIndex];
                oddIndex++;
            } else {
                A[i] = single[singleIndex];
                singleIndex++;
            }
        }

        return A;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}